#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <deque>
#include <list>

using namespace std;

namespace MyPriorityQueue {

	template<class T>
	class Greater {
	public:
		bool operator()(const T& x, const T& y) {
			return x > y;
		}
	};

	template<class T>
	class Less {
	public:
		bool operator()(const T& x, const T& y) {
			return x < y;
		}
	};

	template<class T, class Container = deque<T>, class Compare = Less<T>>
	class priority_queue {
	public:
		priority_queue(const Container con = Container())
			:_con(con)
		{}

		bool empty() {
			return _con.empty();
		}

		size_t size() {
			return _con.size();
		}

		const T& top() const {
			return _con.front();
		}

		void swap(priority_queue& pq) {
			_con.swap(pq._con);
		}

		// 向上调整算法
		void AdjustUp(size_t child) {
			size_t parent = (child - 1) / 2;
			Compare com;
			while (child > 0) {
				bool either = com(_con[parent], _con[child]);

				// 先建立大堆
				//if (_con[parent] < _con[child]) 
				if (com(_con[parent], _con[child])) {
					std::swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else {
					break;
				}
			}
		}

		void push(const T& e) {
			_con.push_back(e);
			AdjustUp(size() - 1);
		}

		void AdjustDown(size_t parent) {
			Compare com;
			size_t child = parent * 2 + 1;
			while (child < size()) {
				// 现在是建大堆，需要找到大的
				if (child + 1 < size() && com(_con[child], _con[child + 1]))
					child++;
				if (com(_con[parent], _con[child])) {
					std::swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else {
					break;
				}
			}
		}

		void pop() {
			std::swap(_con[0], _con[size() - 1]);
			_con.pop_back();
			AdjustDown((int)0);
		}

	private:
		Container _con;
	};
}

void Test03() {
	//MyPriorityQueue::priority_queue<int> pq;
	//// 大堆
	//pq.push(1);
	//pq.push(5);
	//pq.push(3);
	//pq.push(4);
	//pq.push(15);
	//pq.push(7);
	//pq.push(2);
	//while (!pq.empty()) {
	//	cout << pq.top() << " ";
	//	pq.pop();
	//}
	MyPriorityQueue::priority_queue<int, vector<int>, greater<int>> pq;
	pq.push(1);
	pq.push(5);
	pq.push(3);
	pq.push(4);
	pq.push(15);
	pq.push(7);
	pq.push(2);
	while (!pq.empty()) {
		cout << pq.top() << " ";
		pq.pop();
	}
}

int main() {
	Test03();
	return 0;
}